package com.cyj.heapsort;

public class TestHeapSort {
	public static void main(String[] args) {
		int tree[] = {4,5,7,9,1,2,3,8};
		heapSort(tree, tree.length);
		for (int i = 0; i < tree.length; i++) {
			System.out.println(tree[i]+" ");
		}
	}
	/**
	 * @param tree 所要排序的数组
	 * @param n    节点总数（数组的长度）
	 * @param i    要进行堆化操作的节点（父节点）
	 */
	public static void heapify(int tree[], int n, int i) {
		int c1 = 2 * i + 1;// 左子节点
		int c2 = 2 * i + 2;// 右子节点
		int max = i;// 定义一个最大值，初始值为i
		if (c1 < n && tree[c1] > tree[max]) {
			max = c1;// 如果左子节点的值大于父节点，此时把c1赋给max
		}
		if (c2 < n && tree[c2] > tree[max]) {
			max = c2;// 如果右子节点的值大于父节点，此时把c2赋给max
		}
		// 如果max=i，说明子节点没有比父节点更大的值，不需要交换
		// 在max！=i的情况下可以进行交换
		if (max != i) {
			swap(tree, max, i);
			heapify(tree, n, max);// 交换后对子节点继续递归堆化操作
		}
	}

	// 建立完整的堆数组
	public static void buildHeap(int tree[], int n) {
		int lastNode = n - 1;// 末尾节点
		int parent = (lastNode - 1) / 2;// 末尾父节点
		for (int i = parent; i >= 0; i--) {
			heapify(tree,n,i);//从末尾的父节点开始从后往前遍历进行堆化操作
		}
	}
	
	//堆排序
	public static void heapSort(int tree[],int n) {
		buildHeap(tree, n);//建立堆数组
		for(int i = n-1;i>=0;i--) {
			swap(tree,0,i);//将根节点的值与末尾节点的值进行交换
			heapify(tree, i, 0);//再对剩余的节点进行堆化操作
		}
		
	}

	public static void swap(int tree[], int i, int j) {
		int temp = tree[i];
		tree[i] = tree[j];
		tree[j] = temp;
	}
}
